package com.cheung.leetcode.day;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.day
 * @Author :  cheungming
 * @CreateTime : 2024-06-28 07:54:28
 * @Description : 刷墙
 * @Version : 1.0
 */
public class Code2742Test {

    public int paintWalls(int[] cost, int[] time) {
        // 由题意可知 付费刷墙的个数 p+免费刷墙的个数(m) = n,m = n - p
        // 付费刷墙的时间之和 cost[i] >=免费刷墙的时间之和(m), cost[i] >= n-p, cost[i] + p >= n
        // p等于cost[i]个数的，因此cost[i]+1 >=n
        // 本题是求cost[i]的最小和

        int n = cost.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            int c = cost[i];
            // 加1表示免费刷的墙
            int t = time[i] + 1;
            for (int j = n; j > 0; j--) {
                // 此处不直接dp[j-t], 防止j-t<0
                dp[j] = Math.min(dp[j], dp[Math.max(0, j - t)] + c);
            }
        }
        return dp[n];
    }


    @Test
    public void test1() {
        assert paintWalls(new int[]{1, 2, 3, 2}, new int[]{1, 2, 3, 2}) == 3;
    }

    @Test
    public void test2() {
        assert paintWalls(new int[]{2, 3, 4, 2}, new int[]{1, 1, 1, 1}) == 4;
    }
}
